{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #复原 IP 地址"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: restoreIpAddresses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #复原 IP 地址"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个只包含数字的字符串 <code>s</code> ，用以表示一个 IP 地址，返回所有可能从&nbsp;<code>s</code> 获得的 <strong>有效 IP 地址 </strong>。你可以按任何顺序返回答案。</p>\n",
    "\n",
    "<p><strong>有效 IP 地址</strong> 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 <code>0</code>），整数之间用 <code>&#39;.&#39;</code> 分隔。</p>\n",
    "\n",
    "<p>例如：&quot;0.1.2.201&quot; 和 &quot;192.168.1.1&quot; 是 <strong>有效</strong> IP 地址，但是 &quot;0.011.255.245&quot;、&quot;192.168.1.312&quot; 和 &quot;192.168@1.1&quot; 是 <strong>无效</strong> IP 地址。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;25525511135&quot;\n",
    "<strong>输出：</strong>[&quot;255.255.11.135&quot;,&quot;255.255.111.35&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;0000&quot;\n",
    "<strong>输出：</strong>[&quot;0.0.0.0&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;1111&quot;\n",
    "<strong>输出：</strong>[&quot;1.1.1.1&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;010010&quot;\n",
    "<strong>输出：</strong>[&quot;0.10.0.10&quot;,&quot;0.100.1.0&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;10203040&quot;\n",
    "<strong>输出：</strong>[&quot;10.20.30.40&quot;,&quot;102.0.30.40&quot;,&quot;10.203.0.40&quot;]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length &lt;= 3000</code></li>\n",
    "\t<li><code>s</code> 仅由数字组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 93&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/restore-ip-addresses/\">https://leetcode-cn.com/problems/restore-ip-addresses/</a>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [0on3uN](https://leetcode.cn/problems/0on3uN/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [0on3uN](https://leetcode.cn/problems/0on3uN/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"25525511135\"', '\"0000\"', '\"1111\"', '\"010010\"', '\"101023\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        r = []\n",
    "        def restore(count=0, ip='', s=''): # count record split times, ip record ip, s record remaining string\n",
    "            if count == 4:\n",
    "                if s == '':\n",
    "                    r.append(ip[:-1])\n",
    "                return\n",
    "            if len(s) > 0:\n",
    "                restore(count+1, ip+s[0]+'.', s[1:])\n",
    "            if len(s) > 1 and s[0] != '0':\n",
    "                restore(count+1, ip+s[:2]+'.', s[2:])\n",
    "            if len(s) > 2 and s[0] != '0' and int(s[0:3]) < 256:\n",
    "                restore(count+1, ip+s[:3]+'.', s[3:])\n",
    "        restore(0, '', s)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans,path = [],[]\n",
    "        n = len(s)\n",
    "        def backtrack(i):\n",
    "            if len(path)>4:return\n",
    "            if i==n and len(path)==4:\n",
    "                ans.append('.'.join(path[:]))\n",
    "                return\n",
    "            for j in range(i,min(i+3,n)):\n",
    "                t = s[i:j+1]\n",
    "                if (0<int(t)<=255 and t[0]!='0') or (int(t)==0 and len(t)==1):\n",
    "                    path.append(t)\n",
    "                    backtrack(j+1)\n",
    "                    path.pop()\n",
    "                else:break\n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = self.func(s,[],[],4)\n",
    "        for i in range(len(res)):\n",
    "            res[i]=(\".\").join(res[i])\n",
    "        return res\n",
    "        \n",
    "    def func(self, s,arr1,arr2,index):\n",
    "        if index<0:\n",
    "            return arr2\n",
    "        if not s:\n",
    "            if index==0:\n",
    "                arr2.append(arr1)\n",
    "            return arr2\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if int(s[:i+1])>=0 and int(s[:i+1])<=255:\n",
    "                if (len(s[:i+1])<=1) or (len(s[:i+1])>1 and s[0]!=\"0\"):\n",
    "                    arr1.append(s[:i+1])\n",
    "                    self.func(s[i+1:],arr1[:],arr2,index-1)\n",
    "                    arr1.pop()\n",
    "        return arr2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        '''\n",
    "        本质切割问题使用回溯搜索法，本题只能切割三次，所以纵向递归总共四层\n",
    "        因为不能重复分割，所以需要start_index来记录下一层递归分割的起始位置\n",
    "        添加变量point_num来记录逗号的数量[0,3]\n",
    "        '''\n",
    "        self.result.clear()\n",
    "        if len(s) > 12: return []\n",
    "        self.backtracking(s, 0, 0)\n",
    "        return self.result\n",
    "\n",
    "    def backtracking(self, s: str, start_index: int, point_num: int) -> None:\n",
    "        # Base Case\n",
    "        if point_num == 3:\n",
    "            if self.is_valid(s, start_index, len(s)-1):\n",
    "                self.result.append(s[:])\n",
    "            return\n",
    "        # 单层递归逻辑\n",
    "        for i in range(start_index, len(s)):\n",
    "            # [start_index, i]就是被截取的子串\n",
    "            if self.is_valid(s, start_index, i):\n",
    "                s = s[:i+1] + '.' + s[i+1:]\n",
    "                self.backtracking(s, i+2, point_num+1)  # 在填入.后，下一子串起始后移2位\n",
    "                s = s[:i+1] + s[i+2:]    # 回溯\n",
    "            else:\n",
    "                # 若当前被截取的子串大于255或者大于三位数，直接结束本层循环\n",
    "                break\n",
    "    \n",
    "    def is_valid(self, s: str, start: int, end: int) -> bool:\n",
    "        if start > end: return False\n",
    "        # 若数字是0开头，不合法\n",
    "        if s[start] == '0' and start != end:\n",
    "            return False\n",
    "        if not 0 <= int(s[start:end+1]) <= 255:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_valid(self,s,start,end):\n",
    "        if start>end:\n",
    "            return False\n",
    "        if s[start]=='0' and start!=end:\n",
    "            return False\n",
    "        num=0\n",
    "        for i in range(start,end+1):\n",
    "            if not s[i].isdigit():\n",
    "                return False\n",
    "            num=num*10+int(s[i])\n",
    "            if num >255:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def backtracking(self,s,start_index,point_num,current,result):\n",
    "        if point_num==3:\n",
    "            if self.is_valid(s,start_index,len(s)-1):\n",
    "                current+=s[start_index:]\n",
    "                result.append(current)\n",
    "            return\n",
    "        for i in range(start_index,len(s)):\n",
    "            if self.is_valid(s,start_index,i):\n",
    "                sub=s[start_index:i+1]\n",
    "                self.backtracking(s,i+1,point_num+1,current+sub+'.',result)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        result=[]\n",
    "        self.backtracking(s,0,0,\"\",result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        res = []\n",
    "        def dfs(i):\n",
    "            if i == n and len(path) == 4:\n",
    "                res.append('.'.join(path.copy()))\n",
    "                return\n",
    "            if i > 13:\n",
    "                return\n",
    "            for j in range(1,4):\n",
    "                if i+j > n:\n",
    "                    continue\n",
    "                if int(s[i:i+j])>255 or (len(s[i:i+j]) >1 and s[i] == '0'):\n",
    "                    continue\n",
    "                path.append(s[i:i+j])\n",
    "                dfs(i+j)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        res = []\n",
    "\n",
    "        def dfs(i):\n",
    "            # print(i,n)\n",
    "            if i == n and len(path) == 4:\n",
    "                res.append('.'.join(path.copy()))\n",
    "                return\n",
    "            if i > 13:\n",
    "                return\n",
    "            for j in range(1,4):\n",
    "                if i+j > n:\n",
    "                    continue\n",
    "                if int(s[i:i+j])>255 or (len(s[i:i+j]) >1 and s[i] == '0'):\n",
    "                    continue\n",
    "                path.append(s[i:i+j])\n",
    "                dfs(i+j)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        if n > len(\"xxx\") * 4:\n",
    "            return []\n",
    "\n",
    "        def valid(num):\n",
    "            if len(num) <= 0:\n",
    "                return False\n",
    "            if len(num) > 1 and num[0] == '0':\n",
    "                return False\n",
    "            if int(num, 10) > 255:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        v = [\"\"] * 4\n",
    "        for i in range(1, 4):\n",
    "            v[0] = s[0:i]\n",
    "            if not valid(v[0]):\n",
    "                continue\n",
    "            for k in range(1, 4):\n",
    "                v[1] = s[i:k+i]\n",
    "                if not valid(v[1]):\n",
    "                    continue\n",
    "                for m in range(1, 4):\n",
    "                    v[2] = s[k+i:k+i+m]\n",
    "                    v[3] = s[k+i+m:]\n",
    "                    if not valid(v[2]) or not valid(v[3]):\n",
    "                        continue\n",
    "                    ans.append(\".\".join(v))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def restoreIpAddresses(self, s: str):\n",
    "        self.res = []\n",
    "        self.tmp = []\n",
    "        self.dfs(s, 4)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, s, deep):\n",
    "        if deep <= 0 and len(s) > 0:\n",
    "            return None\n",
    "        if deep > len(s):\n",
    "            return None\n",
    "        if deep == len(s):\n",
    "            for c in s:\n",
    "                self.tmp.append(c)\n",
    "            self.res.append(\".\".join(self.tmp))\n",
    "            for c in s:\n",
    "                self.tmp.pop()\n",
    "        else:\n",
    "            for i in range(1, min(4, len(s)+1)):\n",
    "                if self.check(s[:i]):\n",
    "                    self.tmp.append(s[:i])\n",
    "                    self.dfs(s[i:], deep-1)\n",
    "                    self.tmp.pop()\n",
    "        return None\n",
    "\n",
    "    def check(self, s):\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        a = int(s)\n",
    "        if (a == 0 and len(s) > 1) or str(a)!=s:\n",
    "            return False\n",
    "        if a > 255:\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) > 12: return []\n",
    "        path = []\n",
    "        res = []\n",
    "        def rolltraking(index):\n",
    "            if len(path) == 4:\n",
    "                if index == len(s):\n",
    "                    res.append(\".\".join(path))\n",
    "                    return \n",
    "            for i in range(index+1, min(index+4, len(s)+1)):\n",
    "                tmp = s[index:i]\n",
    "                if 0 <= int(tmp) <= 255 and not (tmp[0] == '0' and len(tmp) > 1):\n",
    "                    path.append(tmp)\n",
    "                    rolltraking(i)\n",
    "                    path.pop()\n",
    "        rolltraking(0)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) == 0:\n",
    "            return []\n",
    "        path = []\n",
    "        reslist = []\n",
    "        def isvalid(ss):\n",
    "            l, r = 0, len(ss) - 1\n",
    "            if len(ss) > 1 and ss[0] == '0' or len(ss) == 0:\n",
    "                return False\n",
    "            if int(ss) <= 255 and int(ss) >= 0:\n",
    "                return True\n",
    "            return False\n",
    "            \n",
    "        p = 0\n",
    "        def backtracking(startindex, pointsum):\n",
    "            if pointsum >= 3:\n",
    "                if isvalid(s[startindex:len(s)]):\n",
    "                    ip = \".\".join(path[:]) + \".\" + s[startindex:len(s)]\n",
    "                    reslist.append(ip)\n",
    "                return\n",
    "\n",
    "            for i in range(startindex, len(s)):\n",
    "                if isvalid(s[startindex:i+1]): #注意字符串截取是左闭右开的\n",
    "                   path.append(s[startindex:i+1]) #此处添加的是子串s[startindex:i+1] ， 之前的组合问题添加的是单个字符/数字\n",
    "                   pointsum += 1\n",
    "                else:\n",
    "                    continue\n",
    "                backtracking(i + 1, pointsum)\n",
    "                path.pop()\n",
    "                pointsum -= 1\n",
    "            return\n",
    "        \n",
    "        backtracking(0, 0)\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def check(i,j):\n",
    "            if s[i]==\"0\" and i!=j:\n",
    "                return False\n",
    "            return 0<=int(s[i:j+1])<=255\n",
    "        def dfs(i):\n",
    "            if i>=n and len(path)==4:\n",
    "                res.append(\".\".join(path))\n",
    "                return\n",
    "            if i>=n or len(path)>=4:\n",
    "                return\n",
    "            for j in range(i,min(i+3,n)):\n",
    "                if check(i,j):\n",
    "                    path.append(s[i:j+1])\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        path = []\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) :\n",
    "        if len(s)<4 or len(s)>12:\n",
    "            return []\n",
    "        res=[]\n",
    "        now=\"\"\n",
    "        self.backtracing(s,res,now,0,0)\n",
    "        return res\n",
    "\n",
    "    def backtracing(self,s,res,now,which,lenth):\n",
    "        if which==4 and lenth==len(s):\n",
    "            res.append(now[:-1])\n",
    "            return 0\n",
    "        if which==4 or lenth==len(s):\n",
    "            return 0\n",
    "        for i in range(1,4):\n",
    "            if (len(s)-lenth-i)<=(3-which)*3 and (len(s)-lenth-i)>=3-which and self.ifval(s[lenth:lenth+i]):\n",
    "                self.backtracing(s, res, now+s[lenth:lenth+i]+'.', which+1, lenth+i)\n",
    "\n",
    "    def ifval(self,s):\n",
    "        if len(s)!=1 and s[0]=='0':\n",
    "            return False\n",
    "        if int(s)<=255 and int(s)>=0:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# python3\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) > 12:\n",
    "            return []\n",
    "        path,res = [],[]\n",
    "        def backTrace(index):\n",
    "            if index > len(s):\n",
    "                return\n",
    "            if index == len(s) and len(path) == 4:\n",
    "                res.append('.'.join(path))\n",
    "                return\n",
    "            for i in range(index,len(s)):\n",
    "                if 0 <= int(s[index:i+1]) <= 255:\n",
    "                    # 处理前导0情形\n",
    "                    if s[index] == '0' and len(s[index:i+1]) > 1:\n",
    "                        continue\n",
    "                    path.append(s[index:i+1])\n",
    "                    backTrace(i+1)\n",
    "                    path.pop()\n",
    "        backTrace(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def check(i,j):\n",
    "            if s[i]==\"0\" and i!=j:\n",
    "                return False\n",
    "            return 0<=int(s[i:j+1])<=255\n",
    "        def dfs(index, n, path):\n",
    "            if index>=n and len(path)==4:\n",
    "                res.append(\".\".join(path))\n",
    "                return\n",
    "            if index>=n or len(path)>=4:\n",
    "                return\n",
    "            for j in range(index,min(index+3,n)):\n",
    "                if check(index,j):\n",
    "                    path.append(s[index:j+1])\n",
    "                    dfs(j+1,n,path)\n",
    "                    path.pop()\n",
    "        n = len(s)\n",
    "        res = []\n",
    "    \n",
    "        dfs(0,n,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        # 还是有点难度的\n",
    "        def dfs(segId,segStart):\n",
    "            if segId==SEG_COUNT:\n",
    "                if segStart==len(s):\n",
    "                    ipAddre=\".\".join(str(seg) for seg in segments)\n",
    "                    ans.append(ipAddre)\n",
    "                return\n",
    "            if segStart==len(s):\n",
    "                return\n",
    "            if s[segStart]==\"0\":\n",
    "                segments[segId]=0\n",
    "                dfs(segId+1,segStart+1)\n",
    "            addr=0\n",
    "            for segEnd in range(segStart,len(s)):\n",
    "                addr=addr*10+(ord(s[segEnd])-ord(\"0\"))\n",
    "                if 0<addr<=0xFF:\n",
    "                    segments[segId]=addr\n",
    "                    dfs(segId+1,segEnd+1)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        SEG_COUNT=4\n",
    "        ans=list()\n",
    "        segments=[0]*SEG_COUNT\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        \n",
    "        self.ret = []\n",
    "        def helper(s, sub):\n",
    "            if len(sub) == 4 and len(s) == 0:\n",
    "                self.ret.append(\".\".join(sub))\n",
    "                return\n",
    "            for i in range(1, 4):\n",
    "                if len(s) < i:\n",
    "                    continue\n",
    "                if valid(s[:i]):\n",
    "                    helper(s[i:], sub + [s[:i]])\n",
    "                \n",
    "        \n",
    "        def valid(s):\n",
    "            if not s:\n",
    "                return False\n",
    "            if s[0] == '0' and len(s) == 1:\n",
    "                return True\n",
    "            elif s[0] == '0':\n",
    "                return False\n",
    "            else:\n",
    "                return int(s) < 256\n",
    "        if len(s) > 12:\n",
    "            return []        \n",
    "\n",
    "        helper(s, [])\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        output = []\n",
    "        addrs = [0] * 4\n",
    "        def dfs(sid, index):\n",
    "            if sid == 4:\n",
    "                if index == len(s):\n",
    "                    output.append('.'.join([str(d) for d in addrs]))\n",
    "                return\n",
    "\n",
    "            if index == len(s):\n",
    "                if sid == 4:\n",
    "                    output.append('.'.join([str(d) for d in addrs]))\n",
    "\n",
    "                return\n",
    "            \n",
    "            if s[index] == '0':\n",
    "                addrs[sid] = 0\n",
    "                dfs(sid+1, index+1)\n",
    "\n",
    "\n",
    "            addr = 0\n",
    "            for i in range(index, len(s)):\n",
    "                addr = addr * 10 + (ord(s[i]) - ord('0'))\n",
    "\n",
    "                if  0 < addr <= 255:\n",
    "                    addrs[sid] = addr\n",
    "                    dfs(sid+1, i+1)\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "\n",
    "        dfs(0, 0)\n",
    "\n",
    "\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans,path = [],[]\n",
    "        n = len(s)\n",
    "        def backtrack(i):\n",
    "            if len(path)>4:return #这里必须加一个这个限制条件否则一定会时间超限\n",
    "            if i==n and len(path)==4:\n",
    "                ans.append('.'.join(path[:]))\n",
    "                return\n",
    "            for j in range(i,min(i+3,n)):\n",
    "                t = s[i:j+1]\n",
    "                if (0<int(t)<=255 and t[0]!='0') or (int(t)==0 and len(t)==1):\n",
    "                    path.append(t)\n",
    "                    backtrack(j+1)\n",
    "                    path.pop()\n",
    "                else:break\n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        if len(s) > 12: return res\n",
    "        def backtrack(s, idx, path):\n",
    "            if not s  and idx == 4:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(1, len(s) + 1):\n",
    "                t = s[:i]\n",
    "                if (len(t) > 1 and t[0] == '0') or int(t) > 255: continue\n",
    "                backtrack(s[i:],idx + 1, path + ('.' if len(path) > 0 else '') + s[:i])\n",
    "        backtrack(s, 0, '')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        t = []\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        if n>12:\n",
    "            return []\n",
    "        def backtrack(idx):\n",
    "            if len(t)>4:\n",
    "                return\n",
    "            if idx>n:\n",
    "                return\n",
    "            if idx==n:\n",
    "                if len(t)==4:\n",
    "                    info = '.'.join(t)\n",
    "                    ans.append(info)\n",
    "                return\n",
    "            if s[idx]=='0':\n",
    "                t.append(s[idx])\n",
    "                backtrack(idx+1)\n",
    "                t.pop()\n",
    "                return\n",
    "            else:\n",
    "                for l in [1, 2, 3]:\n",
    "                    if idx+l<=n:\n",
    "                        temp = s[idx:idx+l]\n",
    "                        if 0<=int(temp)<=255:\n",
    "                            t.append(temp)\n",
    "                            backtrack(idx+l)\n",
    "                            t.pop()\n",
    "        backtrack(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) > 12: return []\n",
    "\n",
    "        rnt = []\n",
    "\n",
    "        def _search(tmp, f, t):\n",
    "            # print(tmp, f, t)\n",
    "            if f == len(s):\n",
    "                if len(tmp) == 4:\n",
    "                    rnt.append('.'.join(tmp))\n",
    "                return\n",
    "            \n",
    "            if t - f > 2 or t >= len(s): return\n",
    "            _search(tmp, f, t + 1)\n",
    "\n",
    "            if not (0 <= int(s[f:t+1]) <= 255): return\n",
    "            if len(str(int(s[f:t+1]))) != t - f + 1: return\n",
    "\n",
    "            tmp.append(s[f:t+1])\n",
    "            _search(tmp, t+1, t+1)\n",
    "            tmp.pop()\n",
    "        \n",
    "        _search([], 0, 0)\n",
    "        return rnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) < 4 or len(s) > 12:\n",
    "            return []\n",
    "        \n",
    "        def dfs(index, path):\n",
    "            if index == len(s) and len(path) == 4:\n",
    "                ret.append('.'.join(path))\n",
    "                return\n",
    "            if len(path) >= 4:\n",
    "                return\n",
    "\n",
    "            for i in range(1, 4):\n",
    "                if index + i <= len(s):\n",
    "                    temp = s[index:index+i]\n",
    "                    if (temp[0] == '0' and len(temp) > 1) or (int(temp) > 255):\n",
    "                        continue\n",
    "                    path.append(temp)\n",
    "                    dfs(index + i, path)\n",
    "                    path.pop()\n",
    "        \n",
    "        ret = []\n",
    "        dfs(0, [])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def isvalid(chars):\n",
    "            ## 前导0\n",
    "            if chars[0]=='0' and len(chars)!=1:\n",
    "                return False\n",
    "            for i in chars:\n",
    "                if i<'0' or i>'9':\n",
    "                    return False\n",
    "            num = int(chars)\n",
    "            if num<0 or num>255: return False\n",
    "            return True \n",
    "\n",
    "        n = len(s); path=[];res=[]\n",
    "        def dfs(startidx): \n",
    "            if len(path)>4 : return\n",
    "            if len(path) == 4:\n",
    "                tmps = ''.join(path)  \n",
    "                if len(tmps)==n:\n",
    "                    res.append('.'.join(path))\n",
    "                    return \n",
    "            for i in range(startidx+1,n+1):\n",
    "                chars = s[startidx:i]\n",
    "                if isvalid(chars):\n",
    "                    path.append(chars)\n",
    "                    dfs(i) \n",
    "                    path.pop()  \n",
    "        dfs(0)\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self, s, res, path, start):\n",
    "        if len(path) > 4: return \n",
    "        if len(path) == 4 and start == len(s): res.append('.'.join(path))\n",
    "\n",
    "        for i in range(start, len(s)):\n",
    "            temp = s[start: i + 1]\n",
    "            if int(temp) < 0 or int(temp) > 255 or (len(temp) > 1 and temp[0] == '0'): continue\n",
    "            self.backtracking(s, res, path + [temp], i + 1)\n",
    "\n",
    "\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        self.backtracking(s, res, [], 0)\n",
    "        # for i in range(len(res)):\n",
    "        #     res[i] = ''.join(res[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def process(ind, rs):\n",
    "            if len(rs) > 4:\n",
    "                return\n",
    "\n",
    "            if ind == len(s):\n",
    "                if len(rs) == 4:\n",
    "                    res.append('.'.join(rs))\n",
    "                return\n",
    "\n",
    "            if s[ind] == '0':\n",
    "                process(ind + 1, rs + [s[ind]])\n",
    "            else:\n",
    "                num = 0\n",
    "                for i in range(ind, len(s)):\n",
    "                    num = num * 10 + int(s[i])\n",
    "\n",
    "                    if num <= 255:\n",
    "                        process(i + 1, rs + [str(num)])\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "        process(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) > 12:\n",
    "            return []\n",
    "        def backrack(state, start, res, count):\n",
    "            if count == 4:\n",
    "                if start == len(s):\n",
    "                    res.append('.'.join(list(state)))\n",
    "                    return \n",
    "                else:\n",
    "                    return \n",
    "            for i in range(3):\n",
    "                if start > len(s) -1 or s[start] == '':\n",
    "                    break   \n",
    "                if i == 2 and int(s[start:start + 3]) > 255:\n",
    "                    break\n",
    "                if i >= 1 and len(s[start:start + i + 1]) > 1 and s[start] == '0':\n",
    "                    break\n",
    "                state.append(s[start: start + i + 1])\n",
    "                backrack(state, start + i + 1, res, count + 1)\n",
    "                state.pop()\n",
    "        res = []\n",
    "        backrack([], 0, res, 0)\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        seg_count = 4\n",
    "        segments =[0] * seg_count\n",
    "\n",
    "        def dfs(seg_id, start_index):\n",
    "            if seg_id == seg_count:\n",
    "                if start_index == len(s):\n",
    "                    result.append(\".\".join(str(seg) for seg in segments))\n",
    "                return\n",
    "            \n",
    "            if start_index == len(s):\n",
    "                return\n",
    "            \n",
    "            if s[start_index] == \"0\":\n",
    "                segments[seg_id] = \"0\"\n",
    "                dfs(seg_id+1, start_index+1)\n",
    "\n",
    "            addr = 0\n",
    "            for end_index in range(start_index, len(s)):\n",
    "                addr = addr*10 + (ord(s[end_index]) - ord('0'))\n",
    "                if 0 < addr <= 0xFF:\n",
    "                    segments[seg_id] = addr\n",
    "                    dfs(seg_id+1, end_index+1) \n",
    "                else:\n",
    "                    break \n",
    "\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def backtracking(index):\n",
    "            # if index > len(s):\n",
    "            #     return\n",
    "            if len(path) == 4:\n",
    "                if index == len(s) and '.'.join(path[:]) not in final_path:\n",
    "                    final_path.append('.'.join(path[:]))\n",
    "                return\n",
    "            \n",
    "            for j in range(index,len(s)):\n",
    "                if s[index] == '0':\n",
    "                    path.append(s[index])\n",
    "                    backtracking(index+1)\n",
    "                    path.pop()\n",
    "                else:\n",
    "                    if int(s[index:j+1]) > 0  and int(s[index:j+1]) < 256:\n",
    "                        path.append(s[index:j+1])\n",
    "                        backtracking(j+1)\n",
    "                        path.pop()\n",
    "        \n",
    "        path = []\n",
    "        final_path = []\n",
    "        backtracking(0)\n",
    "        return final_path\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        if not s or len(s) < 4 or len(s) > 12: return []\n",
    "        def backtracking(i, dots, curIP):\n",
    "            if dots == 4 and i == len(s):\n",
    "                res.append(curIP[:-1])\n",
    "                return\n",
    "            if dots > 4: \n",
    "                return\n",
    "            for j in range(i, min(i + 3, len(s))):\n",
    "                if int(s[i:j+1]) < 256 and (s[i] != '0' or i == j):\n",
    "                    backtracking(j + 1, dots + 1, curIP + s[i:j+1] + '.')\n",
    "        backtracking(0, 0, \"\")\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        tmp = []\n",
    "        l = len(s)\n",
    "        if l > 12:\n",
    "            return ans\n",
    "        def dfs(pos, n, tmp):\n",
    "            if pos == l and n == 0:\n",
    "                x = \".\".join(tmp)\n",
    "                ans.append(x)\n",
    "                return\n",
    "\n",
    "            if pos == l and n != 0:\n",
    "                return\n",
    "\n",
    "            for i in range(pos + 1, l + 1):\n",
    "                seg = s[pos:i]\n",
    "                if len(seg) > 1 and seg[0] == '0':\n",
    "                    continue\n",
    "                if len(seg) > 0 and 0 <= int(seg) <= 255:\n",
    "                    tmp.append(seg)\n",
    "                    dfs(i, n - 1, tmp)\n",
    "                    tmp.pop()\n",
    "                elif len(seg) == 0:\n",
    "                    dfs(l, n - 1, tmp)\n",
    "        \n",
    "        dfs(0, 4, tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        if len(s)>3*4:return res\n",
    "        def dfs(index:int, count:int, ans:List[str])->None:\n",
    "            if index==len(s) and count == 4:\n",
    "                res.append(\".\".join(ans))\n",
    "                return\n",
    "            i = 1\n",
    "            while index + i <= len(s):\n",
    "                if int(s[index:index+i])<=255 and len(str(int(s[index:index+i]))) == i:\n",
    "                    ans.append(s[index:index+i])\n",
    "                    dfs(index+i, count+1, ans)\n",
    "                    ans.pop()\n",
    "                i+=1\n",
    "        dfs(0, 0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res, n = [], len(s)\n",
    "\n",
    "        def dfs(i, path):\n",
    "            if len(path) == 4:\n",
    "                if i == n:\n",
    "                    ips = '.'.join([str(seg) for seg in path])\n",
    "                    res.append(ips)\n",
    "                return\n",
    "            \n",
    "            if i == n:\n",
    "                return\n",
    "\n",
    "            if s[i] == '0':\n",
    "                dfs(i+1, path + [0])\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                addr = int(s[i:j+1])\n",
    "                if 0<addr<=255:\n",
    "                    dfs(j+1, path+[addr])\n",
    "                else:\n",
    "                    break\n",
    "        dfs(0, [])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if s[12:13]:\n",
    "            return []\n",
    "\n",
    "        @cache\n",
    "        def cut(i, j, x):\n",
    "            ws = j - i\n",
    "            if x > ws or ws == 0 or ws > 3 * x:\n",
    "                return []\n",
    "            if x == 1:\n",
    "                if ws == 1:\n",
    "                    return [s[i:j]]\n",
    "                v = int(s[i:j])\n",
    "                if v <= 255 and s[i] != '0':\n",
    "                    return [s[i:j]]\n",
    "                return []\n",
    "\n",
    "            rs = []\n",
    "            a1 = s[i]\n",
    "            rs.extend([f'{a1}.{a}' for a in cut(i + 1, j, x - 1)])\n",
    "            if a1 != '0':\n",
    "                a2 = s[i: i + 2]\n",
    "                rs.extend([f'{a2}.{a}' for a in cut(i + 2, j, x - 1)])\n",
    "                a3 = s[i: i + 3]\n",
    "                if int(a3) < 256:\n",
    "                    rs.extend([f'{a3}.{a}' for a in cut(i + 3, j, x - 1)])\n",
    "            return rs\n",
    "\n",
    "        l = len(s)\n",
    "        return cut(0, l, 4)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        self.res = []\n",
    "        if len(s)>12 or len(s)<4:return []\n",
    "        def check(s):\n",
    "            if len(s)<=0 or len(s)>3:return False\n",
    "            if s[0]=='0' and len(s)>1:return False\n",
    "            if eval(s)<0 or eval(s)>255:return False\n",
    "            return True\n",
    "\n",
    "        def dfs(loc):\n",
    "            if len(loc)==3:\n",
    "                if check(s[loc[-1]+1:]):\n",
    "                    self.res.append(s[:loc[0]+1]+'.'+s[loc[0]+1:loc[1]+1]+'.'+s[loc[1]+1:loc[2]+1]+'.'+s[loc[2]+1:])\n",
    "                return \n",
    "            if len(loc)>0:\n",
    "                for i in range(1+loc[-1],len(s)):\n",
    "                    if check(s[loc[-1]+1:i+1]):dfs(loc+[i])\n",
    "            else:\n",
    "                for i in range(len(s)):\n",
    "                    if check(s[:i+1]):dfs(loc+[i])\n",
    "        dfs([])\n",
    "        return self.res   \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        SEG_COUNT = 4\n",
    "        ans = list()\n",
    "        segments = [0] * SEG_COUNT\n",
    "        \n",
    "        def backtrack(segId: int, segStart: int):\n",
    "            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案\n",
    "            if segId == SEG_COUNT:\n",
    "                if segStart == len(s):\n",
    "                    ipAddr = \".\".join(str(seg) for seg in segments)\n",
    "                    ans.append(ipAddr)\n",
    "                return\n",
    "            \n",
    "            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯\n",
    "            if segStart == len(s):\n",
    "                return\n",
    "\n",
    "            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0\n",
    "            if s[segStart] == \"0\":\n",
    "                segments[segId] = 0\n",
    "                backtrack(segId + 1, segStart + 1)\n",
    "            \n",
    "            # 一般情况，枚举每一种可能性并递归\n",
    "            addr = 0\n",
    "            for segEnd in range(segStart, len(s)):\n",
    "                addr = addr * 10 + (ord(s[segEnd]) - ord(\"0\"))\n",
    "                if 0 < addr <= 0xFF:\n",
    "                    segments[segId] = addr\n",
    "                    backtrack(segId + 1, segEnd + 1)\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "\n",
    "        backtrack(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        if len(s) > 12: return res\n",
    "        def backtrack(s, idx, path):\n",
    "            if not s  and idx == 4:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(1, len(s) + 1):\n",
    "                t = s[:i]\n",
    "                if (len(t) > 1 and t[0] == '0') or int(t) > 255: return\n",
    "                backtrack(s[i:],idx + 1, path + ('.' if len(path) > 0 else '') + s[:i])\n",
    "        backtrack(s, 0, '')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans, cur = [], []\n",
    "        L = len(s)\n",
    "\n",
    "        def dfs(l):\n",
    "            if len(cur) > 4:  #cur已经超过四个了，剪枝\n",
    "                return\n",
    "            if l == L and len(cur) == 4:   #满足要求，加入ans\n",
    "                ans.append('.'.join(cur))\n",
    "                return\n",
    "            for i in range(l+1, min(l+4, L+1)):  #最多3个\n",
    "                curr = s[l:i]\n",
    "                if (len(curr) > 1 and curr[0] == '0') or int(curr) > 255:\n",
    "                    break\n",
    "                cur.append(curr[:])\n",
    "                dfs(i)\n",
    "                cur.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def dfs(u, ip):\n",
    "            print(u, ip)\n",
    "            if u == n:\n",
    "                if len(ip) == 4:\n",
    "                    ans.append('.'.join(ip))\n",
    "                return\n",
    "                \n",
    "            if len(ip) == 4:\n",
    "                return\n",
    "\n",
    "            if s[u] == '0':\n",
    "                ip.append('0')\n",
    "                dfs(u + 1, ip)\n",
    "                return\n",
    "\n",
    "            num = 0\n",
    "            for i in range(u, n):\n",
    "                num = num * 10 + int(s[i])\n",
    "                if num <= 255:\n",
    "                    # ip.append(str(num))\n",
    "                    dfs(i + 1, ip + [str(num)])\n",
    "                    # ip.pop()\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        dfs(0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if i == len(s):\n",
    "                if len(path) == 4:\n",
    "                    ans.append('.'.join(path))\n",
    "                return\n",
    "            if len(path) == 4:\n",
    "                return\n",
    "            if s[i] == '0':\n",
    "                path.append('0')\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                for j in range(i,len(s)):\n",
    "                    if int(s[i:j + 1]) <= 255:\n",
    "                        path.append(s[i:j + 1])\n",
    "                        dfs(j + 1)\n",
    "                        path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        @lru_cache(None)\n",
    "        def split(i, num):\n",
    "            if i >= n:  return []\n",
    "            if num == 1:\n",
    "                if i == n - 1 or (s[i] != \"0\" and int(s[i:]) <= 255):\n",
    "                    return [s[i:]]\n",
    "                else:\n",
    "                    return []\n",
    "            \n",
    "            if s[i] == \"0\":\n",
    "                subset = split(i+1, num-1)\n",
    "                if not subset:  return []\n",
    "                else:   return [\"0.\" + i for i in subset]\n",
    "            \n",
    "            ans = []\n",
    "            for j in range(1, 3):\n",
    "                subset = split(i+j, num-1)\n",
    "                if subset:  ans.extend([s[i:i+j] + \".\" + k for k in subset])\n",
    "            \n",
    "            if int(s[i:i+3]) <= 255:\n",
    "                subset = split(i+3, num-1)\n",
    "                if subset:  ans.extend([s[i:i+3] + \".\" + k for k in subset])\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        return split(0, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        if n < 4 or 12 < n:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def backtrace(idx: int) -> None:\n",
    "            if len(path) == 4:\n",
    "                if idx == n:\n",
    "                    res.append('.'.join(path))\n",
    "                return\n",
    "            if idx == n:\n",
    "                return \n",
    "                \n",
    "            if s[idx] == '0':\n",
    "                path.append('0')\n",
    "                backtrace(idx + 1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                for i in range(idx, n):\n",
    "                    cur_num = int(s[idx: i + 1])\n",
    "                    if 0 <= cur_num <= 255:\n",
    "                        path.append(str(cur_num))\n",
    "                        backtrace(i + 1)\n",
    "                        path.pop()\n",
    "                    else:\n",
    "                        break\n",
    "        \n",
    "        backtrace(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ips = []\n",
    "        if n < 4 or n > 12:\n",
    "            return ips\n",
    "        for i1 in range(min(4, n)):\n",
    "            seg1 = s[:i1 + 1]\n",
    "            if not self.check_ip(seg1):\n",
    "                continue\n",
    "            for i2 in range(i1 + 1, min(i1 + 4, n)):\n",
    "                seg2 = s[i1 + 1:i2 + 1]\n",
    "                if not self.check_ip(seg2):\n",
    "                    continue\n",
    "                for i3 in range(i2 + 1, min(i2 + 4, n)):\n",
    "                    seg3 = s[i2 + 1:i3 + 1]\n",
    "                    seg4 = s[i3 + 1:]\n",
    "                    if self.check_ip(seg3) and self.check_ip(seg4):\n",
    "                        ips.append(seg1 + \".\" + seg2 + \".\" + seg3 + \".\" + seg4)\n",
    "        return ips\n",
    "\n",
    "    def check_ip(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n == 0 or n > 3:\n",
    "            return False\n",
    "        if s[0] == \"0\" and n > 1:\n",
    "            return False\n",
    "        int_val = int(s)\n",
    "        return int_val >= 0 and int_val <= 255"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "    res = []\n",
    "    path = []\n",
    "    n = len(s)\n",
    "\n",
    "    def dfs(index):\n",
    "      if len(path) > 4: return\n",
    "      if len(path) == 4 and index == n: \n",
    "        res.append('.'.join(path))\n",
    "        return\n",
    "      \n",
    "      for i in range(index, n):\n",
    "        str = s[index : i + 1]\n",
    "        if int(str) < 256 and (str[0] != '0' or str == '0'):\n",
    "          path.append(str)\n",
    "          dfs(i + 1)\n",
    "          path.pop()\n",
    "\n",
    "    dfs(0)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "\n",
    "        if n < 4 or n > 12:\n",
    "            return res\n",
    "\n",
    "        def dfs(path, start):\n",
    "            if len(path) > 4:\n",
    "                return\n",
    "            \n",
    "            if len(path) == 4 and start == n:\n",
    "                res.append('.'.join(path))\n",
    "                return\n",
    "            \n",
    "            for i in range(start, n):\n",
    "                seg = s[start: i + 1]\n",
    "                if int(seg) > 255 or (s[start] == '0' and len(seg) > 1):\n",
    "                    break\n",
    "                dfs(path + [seg], i + 1)\n",
    "        \n",
    "        dfs([], 0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if True:\n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if \"\".join(paths) == s and len(paths) == 4:\n",
    "                    results.append(\".\".join(paths))\n",
    "                    return\n",
    "                if len(paths)>4:\n",
    "                    return\n",
    "                for i in range(index, len(s)):\n",
    "                    subpath = s[index:i+1]\n",
    "                    if int(subpath)<0 or int(subpath)>255:\n",
    "                        continue\n",
    "                    if len(subpath) >=2 and subpath.startswith(\"0\"):\n",
    "                        continue\n",
    "                    dfs(paths + [s[index:i+1]], i+1)\n",
    "            dfs([], 0)\n",
    "            return results\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        else:\n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if \"\".join(paths) == s and len(paths) == 4:\n",
    "                    results.append(paths)\n",
    "                    return\n",
    "                if len(paths) >4:\n",
    "                    return\n",
    "\n",
    "                for i in range(index,len(s)):\n",
    "                    t = s[index:i+1]\n",
    "                    if not (int(t) >=0 and int(t) <=255):\n",
    "                        continue \n",
    "                    if len(t)>=2 and t.startswith(\"0\"):\n",
    "                        continue\n",
    "                    dfs(paths +[s[index:i+1]], i+1)\n",
    "            dfs([], 0)\n",
    "            print(results)\n",
    "            results = [\".\".join(i) for i in results]\n",
    "            return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans, cur = [], []\n",
    "        L = len(s)\n",
    "\n",
    "        def dfs(l):\n",
    "            if len(cur) > 4: #cur已经超过四个了，剪枝\n",
    "                return\n",
    "            if l == L and len(cur) == 4: #满足要求，加入ans\n",
    "                ans.append('.'.join(cur))\n",
    "                return\n",
    "            for i in range(l+1, min(l+4, L+1)):  #最多3个\n",
    "                curr = s[l:i]\n",
    "                if (len(curr) > 1 and curr[0] == '0') or int(curr) > 255:\n",
    "                    continue\n",
    "                cur.append(curr[:])\n",
    "                dfs(i)\n",
    "                cur.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def is_val(ss,start,i):\n",
    "            if ss[0]=='0' and len(ss)!=1: #0开头\n",
    "                return False\n",
    "            elif 0<=int(ss)<=255:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        def search(start):\n",
    "            if start==len(s) and len(path)==4:\n",
    "                result.append('.'.join(path))\n",
    "                return\n",
    "            if len(path)==4:\n",
    "                return\n",
    "            for i in range(start,min(len(s),start+3)):\n",
    "                if is_val(s[start:i+1],start,i):\n",
    "                    path.append(s[start:i+1])\n",
    "                    print(path,i)\n",
    "                    search(i+1)\n",
    "                    path.pop(-1)\n",
    "            return\n",
    "        path = []\n",
    "        result = []\n",
    "        search(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def dfs(n,arr,k):\n",
    "            if k <= 0 :\n",
    "                return arr\n",
    "            ans = []\n",
    "            for idx in range(len(arr)):\n",
    "                for i in range(arr[idx][-1]+1,n+1):\n",
    "                    ans.append(arr[idx] + [i])\n",
    "            return dfs(n,ans,k-1)\n",
    "        return dfs(n,[[i] for i in range(1,n-k+2)],k-1)\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def add(s,arr):\n",
    "            ss = \"\"\n",
    "            idx = 0\n",
    "            for num in arr:\n",
    "                ss += (s[idx:num] + \".\")\n",
    "                idx = num\n",
    "            return ss + s[idx:]\n",
    "        def judge(s):\n",
    "            ss = s.split(\".\")\n",
    "            for sss in ss:\n",
    "                if int(sss) > 255 or (sss[0] == \"0\" and len(sss) > 1):\n",
    "                    return False\n",
    "            return True\n",
    "        n = len(s)\n",
    "        if n == 4:\n",
    "            return [f\"{s[0]}.{s[1]}.{s[2]}.{s[3]}\"]\n",
    "        elif n < 4:\n",
    "            return []\n",
    "        elif n == 12:\n",
    "            ss = f\"{s[:3]}.{s[3:6]}.{s[6:9]}.{s[9:12]}\"\n",
    "            if judge(ss):\n",
    "                return [ss]\n",
    "            else:\n",
    "                return []\n",
    "\n",
    "        if len(s) > 12:\n",
    "            return []\n",
    "        ans = []\n",
    "        conbines = self.combine(n-1,3)\n",
    "        for conbine in conbines:\n",
    "            if conbine[1]-conbine[0] > 3 or conbine[2]-conbine[1] > 3 or n-conbine[2] > 3:\n",
    "                continue\n",
    "            ss = add(s,conbine)\n",
    "            if judge(ss):\n",
    "                ans.append(ss)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) > 12 or len(s) < 4:\n",
    "            return []\n",
    "        res = []\n",
    "        # 隔板法，枚举三个隔板位置\n",
    "        for i in range(1, len(s) - 2):\n",
    "            for j in range(i+1, len(s) - 1):\n",
    "                for k in range(j+1, len(s)):\n",
    "                    if self.checked(s, i, j, k):\n",
    "                        ans = f\"{int(s[0:i])}.{int(s[i:j])}.{int(s[j:k])}.{int(s[k:])}\"\n",
    "                        res.append(ans)\n",
    "        return res\n",
    "    \n",
    "    def checked(self,s, i, j, k):\n",
    "        str1 = s[0:i]\n",
    "        if(len(str1) > 1 and str1[0] == '0') or int(str1) > 255:\n",
    "            return False\n",
    "        \n",
    "        str2 = s[i:j]\n",
    "        if(len(str2) > 1 and str2[0] == \"0\") or int(str2) > 255:\n",
    "            return False\n",
    "\n",
    "        str3 = s[j:k]\n",
    "        if(len(str3) > 1 and str3[0] == \"0\") or int(str3) > 255:\n",
    "            return False\n",
    "        \n",
    "        str4 = s[k:]\n",
    "        if(len(str4) > 1 and str4[0] == \"0\") or int(str4) > 255:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def cur(i,path):\n",
    "            if len(path)>4:return\n",
    "            if i==n and len(path)==4:\n",
    "                ans.append('.'.join(path)) \n",
    "                return\n",
    "            for x in range(i,n):\n",
    "                if x-i<=2:\n",
    "                    t=s[i:x+1]\n",
    "                    if (len(t) > 1 and t[0] == '0') or int(t) > 255: continue\n",
    "\n",
    "                    path.append(t)\n",
    "                    cur(x+1,path)\n",
    "                    path.pop()\n",
    "\n",
    "                \n",
    "\n",
    "        ans=[]\n",
    "        n=len(s)\n",
    "        cur(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        SEG_COUNT = 4\n",
    "        ans = list()\n",
    "        segments = [0] * SEG_COUNT\n",
    "        \n",
    "        def dfs(segId: int, segStart: int):\n",
    "            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案\n",
    "            if segId == SEG_COUNT:\n",
    "                if segStart == len(s):\n",
    "                    ipAddr = \".\".join(str(seg) for seg in segments)\n",
    "                    ans.append(ipAddr)\n",
    "                return\n",
    "            \n",
    "            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯\n",
    "            if segStart == len(s):\n",
    "                return\n",
    "\n",
    "            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0\n",
    "            if s[segStart] == \"0\":\n",
    "                segments[segId] = 0\n",
    "                dfs(segId + 1, segStart + 1)\n",
    "            \n",
    "            # 一般情况，枚举每一种可能性并递归\n",
    "            addr = 0\n",
    "            for segEnd in range(segStart, len(s)):\n",
    "                addr = addr * 10 + (ord(s[segEnd]) - ord(\"0\"))\n",
    "                if 0 < addr <= 0xFF:\n",
    "                    segments[segId] = addr\n",
    "                    dfs(segId + 1, segEnd + 1)\n",
    "                else:\n",
    "                    break\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        def dfs(s, st, path):\n",
    "            if st == len(s) and len(path) == 4:\n",
    "                res.append('.'.join(path))\n",
    "                return\n",
    "            if st == len(s) or len(path) == 4:\n",
    "                return\n",
    "            \n",
    "            for ed in range(st+1, min(st+4, len(s)+1)):\n",
    "                if ed > st + 1 and s[st] == '0':\n",
    "                    continue\n",
    "                if 0 <= int(s[st:ed]) < 256:\n",
    "                    path.append(s[st:ed])\n",
    "                    dfs(s, ed, path)\n",
    "                    path.pop()\n",
    "        \n",
    "        dfs(s, 0, [])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        t = []\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        if n>12:\n",
    "            return []\n",
    "        def backtrack(idx):\n",
    "            # if len(t)>4:\n",
    "            #     return\n",
    "            if idx>n:\n",
    "                return\n",
    "            if idx==n:\n",
    "                if len(t)==4:\n",
    "                    info = '.'.join(t)\n",
    "                    ans.append(info)\n",
    "                return\n",
    "            if s[idx]=='0':\n",
    "                t.append(s[idx])\n",
    "                backtrack(idx+1)\n",
    "                t.pop()\n",
    "                return\n",
    "            else:\n",
    "                for l in [1, 2, 3]:\n",
    "                    if idx+l<=n:\n",
    "                        temp = s[idx:idx+l]\n",
    "                        if 0<=int(temp)<=255:\n",
    "                            t.append(temp)\n",
    "                            backtrack(idx+l)\n",
    "                            t.pop()\n",
    "        backtrack(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        # 遍历每个数字(N步)，对每个数字的选项：拼接到前一个分段，或者作为新的分段\n",
    "        # 只有‘.’分割，\n",
    "        result = []\n",
    "        length = len(s)\n",
    "        \"\"\"将字符串分成 4 个部分，一次判断每个部分是否满足：是否为空;是否存在先导 0;数值是否大于 255\"\"\"\n",
    "        def isValid(seg): # 当前分段字符是否有效\n",
    "            # print(int(seg),int(seg)<=255 and (seg[0]!='0' or int(seg)=='0'))\n",
    "            return int(seg)<=255 and (seg[0]!='0' or seg==\"0\") #会有'00'情况 不能用int()=0\n",
    "\n",
    "        def dfs(s,i,segID,seg,ip,result):\n",
    "            if i==length and segID==3 and isValid(seg):\n",
    "                result.append(ip+seg) #之前的分段+当前的seg\n",
    "                return\n",
    "            # 对每个数字的选项：拼接到前一个分段，或者作为新的分段\n",
    "            elif (i<len(s) and segID<=3):\n",
    "                ch = s[i]\n",
    "                if isValid(seg+ch):#是合法的,ip是上一个分段\n",
    "                    dfs(s,i+1,segID,seg+ch,ip,result)\n",
    "                if len(seg)>0 and segID<3: #seg原来有值，分段索引小于\n",
    "                    dfs(s,i+1,segID+1,\"\"+ch,ip+seg+\".\",result)\n",
    "        dfs(s,0,0,\"\",\"\",result)\n",
    "        return result\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        t = []\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        if n>12:\n",
    "            return []\n",
    "        def backtrack(idx):\n",
    "            # if len(t)>4:\n",
    "            #     return\n",
    "            if idx>n:\n",
    "                return\n",
    "            if idx==n:\n",
    "                if len(t)==4:\n",
    "                    info = '.'.join(t)\n",
    "                    ans.append(info)\n",
    "                return\n",
    "            if s[idx]=='0':\n",
    "                t.append(s[idx])\n",
    "                backtrack(idx+1)\n",
    "                t.pop()\n",
    "                return\n",
    "            else:\n",
    "                for l in [1, 2, 3]:\n",
    "                    if idx+l<=n:\n",
    "                        temp = s[idx:idx+l]\n",
    "                        if 0<=int(temp)<=255:\n",
    "                            t.append(temp)\n",
    "                            backtrack(idx+l)\n",
    "                            t.pop()\n",
    "        backtrack(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        SEG_COUNT = 4\n",
    "        ans = list()\n",
    "        segments = [0] * SEG_COUNT\n",
    "\n",
    "        def dfs(segId, segStart):\n",
    "            # 如果找到了4段IP地址并且遍历完了字符串\n",
    "            if segId == SEG_COUNT:\n",
    "                if segStart == len(s):\n",
    "                    ipAddr = \".\".join(str(seg) for seg in segments)\n",
    "                    ans.append(ipAddr)\n",
    "                return\n",
    "            \n",
    "            # 如果还没有找到4段IP地址就已经完成了遍历，那么提前回溯\n",
    "            if segStart == len(s):\n",
    "                return \n",
    "            \n",
    "            # 由于不能有前导0，如果当前数字为0，那么这一段IP地址只能为0\n",
    "            if s[segStart] == \"0\":\n",
    "                segments[segId] = 0\n",
    "                dfs(segId + 1, segStart + 1)\n",
    "            \n",
    "            # 一般情况下，枚举每一种可能\n",
    "            addr = 0\n",
    "            for segEnd in range(segStart, len(s)):\n",
    "                addr = 10 * addr + ord(s[segEnd]) - ord('0')\n",
    "                if 0 < addr <= 255:\n",
    "                    segments[segId] = addr\n",
    "                    dfs(segId + 1, segEnd + 1)\n",
    "                else:\n",
    "                    break\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans, temp = [], []\n",
    "        if n > 12:return ans\n",
    "        def dfs(index, begin):\n",
    "            if index == 4 and begin == n:\n",
    "                ans.append('.'.join(temp))\n",
    "                return\n",
    "            if begin > n - 1:return\n",
    "            if s[begin] == '0':\n",
    "                temp.append(s[begin])\n",
    "                dfs(index + 1, begin + 1)\n",
    "                temp.pop()\n",
    "            \n",
    "            total = 0\n",
    "            for i in range(begin, n):\n",
    "                total = total * 10 + int(s[i])\n",
    "                if 0 < total <= 255:\n",
    "                    temp.append(str(total))\n",
    "                    dfs(index + 1, i + 1)\n",
    "                    temp.pop()\n",
    "                else:\n",
    "                    break\n",
    "                \n",
    "            \n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        res = []\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n and len(path) == 4:\n",
    "                res.append('.'.join(path.copy()))\n",
    "                return\n",
    "            if i > 13:\n",
    "                return\n",
    "            for j in range(1,4):\n",
    "                if i+j > n:\n",
    "                    continue\n",
    "                if int(s[i:i+j])>255 or (len(s[i:i+j]) >1 and s[i] == '0'):\n",
    "                    continue\n",
    "                path.append(s[i:i+j])\n",
    "                dfs(i+j)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if True:\n",
    "            if len(s) > 12:\n",
    "                return []\n",
    "            path,res = [],[]\n",
    "            def backTrace(index):\n",
    "                if index > len(s):\n",
    "                    return\n",
    "                if index == len(s) and len(path) == 4:\n",
    "                    res.append('.'.join(path))\n",
    "                    return\n",
    "                for i in range(index,len(s)):\n",
    "                    if 0 <= int(s[index:i+1]) <= 255:\n",
    "                        # 处理前导0情形\n",
    "                        if s[index] == '0' and len(s[index:i+1]) > 1:\n",
    "                            continue\n",
    "                        path.append(s[index:i+1])\n",
    "                        backTrace(i+1)\n",
    "                        path.pop()\n",
    "            backTrace(0)\n",
    "            return res\n",
    "\n",
    "        elif False:\n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if \"\".join(paths) == s and len(paths) == 4:\n",
    "                    results.append(\".\".join(paths))\n",
    "                    return\n",
    "                if index>len(s):\n",
    "                    return\n",
    "                for i in range(index, len(s)):\n",
    "                    subpath = s[index:i+1]\n",
    "                    if int(subpath)<0 or int(subpath)>255:\n",
    "                        continue\n",
    "                    if len(subpath) >=2 and subpath.startswith(\"0\"):\n",
    "                        continue\n",
    "                    dfs(paths + [s[index:i+1]], i+1)\n",
    "            dfs([], 0)\n",
    "            return results\n",
    "\n",
    "        else:\n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if \"\".join(paths) == s and len(paths) == 4:\n",
    "                    results.append(paths)\n",
    "                    return\n",
    "                if len(paths) >4:\n",
    "                    return\n",
    "\n",
    "                for i in range(index,len(s)):\n",
    "                    t = s[index:i+1]\n",
    "                    if not (int(t) >=0 and int(t) <=255):\n",
    "                        continue \n",
    "                    if len(t)>=2 and t.startswith(\"0\"):\n",
    "                        continue\n",
    "                    dfs(paths +[s[index:i+1]], i+1)\n",
    "            dfs([], 0)\n",
    "            print(results)\n",
    "            results = [\".\".join(i) for i in results]\n",
    "            return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s)>=13:\n",
    "            return []\n",
    "        def isvalid(string):\n",
    "            try:\n",
    "                tmp=int(string)\n",
    "                if len(string)>1 and string[0]=='0':\n",
    "                    return False\n",
    "                if 0<=tmp<=255:\n",
    "                    return True\n",
    "                return False            \n",
    "            except:\n",
    "                return False\n",
    "        res,path=[],[]\n",
    "        def dfs(startindex):\n",
    "            if len(path)==3:\n",
    "                try:\n",
    "                    if 0<=int(s[startindex:])<=255:\n",
    "                        xi=s[startindex:]\n",
    "                        if len(s[startindex:])>1 and s[startindex:][0]=='0':\n",
    "                            return\n",
    "                        tmp=path+[s[startindex:]]\n",
    "                        res.append('.'.join(tmp))\n",
    "                        return\n",
    "                    return\n",
    "                except:\n",
    "                    return\n",
    "            for i in range(startindex,len(s)):\n",
    "                if isvalid(s[startindex:i+1]):\n",
    "                    path.append(s[startindex:i+1])\n",
    "                    dfs(i+1)\n",
    "                    path.pop()\n",
    "                else:\n",
    "                    continue\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        start = 0\n",
    "        end = 0\n",
    "        res = []\n",
    "        for i in range(0,3):\n",
    "            for j in range(i+1,min(len(s),i+4)):\n",
    "                for k in range(j+1,min(len(s),j+4)):\n",
    "                    if k+4 >= len(s) and k+1 < len(s) and self.check(s[0:i+1]) and self.check(s[i+1:j+1]) and self.check(s[j+1:k+1]) and self.check(s[k+1:]):\n",
    "                        res.append(s[0:i+1] + '.' + s[i+1:j+1] + '.' + s[j+1:k+1] + '.' + s[k+1:])\n",
    "                        print(res)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def check(self,s):\n",
    "        res = 0\n",
    "        if len(s)>1 and s[0] == '0':\n",
    "            return False\n",
    "        res = int(s)\n",
    "        if res>=0 and res <= 255:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        def check(s):\n",
    "            if len(s) <= 0:\n",
    "                return False\n",
    "            if s != '0' and s[0] == '0':\n",
    "                return False\n",
    "            elif int(s) > 255 or int(s) < 0:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        def dfs(index,path):\n",
    "            if len(path) >= 3:\n",
    "                if check(s[index:]):\n",
    "                    path.append(s[index:])\n",
    "                    res.append(path.copy())\n",
    "                    path.pop()\n",
    "                return\n",
    "\n",
    "            for i in range(1,4):\n",
    "                if check(s[index:index+i]):\n",
    "                    path.append(s[index:index+i])\n",
    "                    dfs(index+i,path)\n",
    "                    path.pop()\n",
    "        \n",
    "        dfs(0, [])\n",
    "        res1 = []\n",
    "        for rs in res:\n",
    "            tp = ''\n",
    "            for si in rs:\n",
    "                tp += si\n",
    "                tp += '.'\n",
    "            res1.append(tp[:-1])\n",
    "        return res1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "\n",
    "        ip = [''] * 4\n",
    "        res = []\n",
    "        for i1 in range(1, len(s)):\n",
    "            if self.is_seg(s[0:i1]):\n",
    "                ip[0] = s[0:i1]\n",
    "            else:\n",
    "                break\n",
    "            for i2 in range(i1 + 1, len(s)):\n",
    "                if self.is_seg(s[i1:i2]):\n",
    "                    ip[1] = s[i1:i2]\n",
    "                else:\n",
    "                    break\n",
    "                for i3 in range(i2 + 1, len(s)):\n",
    "                    if self.is_seg(s[i2:i3]) and self.is_seg(s[i3:len(s)]):\n",
    "                        ip[2] = s[i2:i3]\n",
    "                        ip[3] = s[i3:]\n",
    "                        res.append(\".\".join(ip))\n",
    "        return res\n",
    "\n",
    "    def is_seg(self, s):\n",
    "        if len(str(int(s))) != len(s):\n",
    "            return False\n",
    "        \n",
    "        if int(s) > 255:\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        N = len(s) \n",
    "        if N < 4 or N > 12: \n",
    "            return [] \n",
    "        ans = [] \n",
    "        cur = [] \n",
    "        @cache \n",
    "        def check(d): \n",
    "            leng = len(d) \n",
    "            val = int(d) \n",
    "            if leng < 1 or leng > 3 or (leng==2 and val<10) or (leng==3 and (val<100 or val>255)): \n",
    "                return False \n",
    "            return True \n",
    "\n",
    "        def dfs(i: int ):  \n",
    "            if len(cur) == 3:                   # 已得到ip前3个数\n",
    "                if i<N and check(s[i:]):        # 判断第四个数是否合法\n",
    "                    cur.append(s[i:]) \n",
    "                    ans.append('.'.join(cur)) \n",
    "                    cur.pop() \n",
    "                return \n",
    "            for k in range(3): \n",
    "                if i+k<N and check(s[i:i+k+1]): # 检查当前位置的1,2,3位组合\n",
    "                    cur.append(s[i:i+k+1]) \n",
    "                    dfs(i+k+1) \n",
    "                    cur.pop() \n",
    "        dfs(0) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        \n",
    "        def judge(p):\n",
    "            if not p or (p.startswith('0') and len(p) != 1):\n",
    "                return False\n",
    "            return 0 <= int(p) <= 255\n",
    "        \n",
    "        def dsf(p, t, m):\n",
    "            nonlocal ans\n",
    "            if t == 1:\n",
    "                if judge(p):\n",
    "                    ans.append(f'{m}.{p}')\n",
    "                    return\n",
    "            for i in range(1, min(len(p), 4)):\n",
    "                if not judge(p[:i]):\n",
    "                    continue\n",
    "                dsf(p[i:], t - 1, f'{m}.{p[:i]}' if m else p[:i])\n",
    "        if not 4 <=len(s) <= 12: return []\n",
    "        dsf(s, 4, '')\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        if n > 12:\n",
    "            return []\n",
    "        ans,tem = [],[]\n",
    "\n",
    "        def dfs(tem,idx):\n",
    "            if len(tem) == 4 and idx == n:\n",
    "                ans.append('.'.join(tem))\n",
    "                return\n",
    "            for i in range(1,4):\n",
    "                if idx + i > n:\n",
    "                    continue\n",
    "                sub = s[idx:idx+i]\n",
    "                if len(sub) > 1 and sub[0] == '0':\n",
    "                    continue\n",
    "                if int(sub) > 255:\n",
    "                    continue\n",
    "                else:\n",
    "                    tem.append(sub)\n",
    "                    dfs(tem,idx+i)\n",
    "                    tem.pop()\n",
    "        dfs(tem,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s)>12:\n",
    "           return []\n",
    "        path,res=[],[]\n",
    "\n",
    "        def backTrace(index):\n",
    "            if index>len(s):\n",
    "                return\n",
    "            if index==len(s) and len(path)==4:\n",
    "                res.append('.'.join(path))\n",
    "                return\n",
    "            for i in range(index,len(s)):\n",
    "                if 0<=int(s[index:i+1])<=255:\n",
    "                    if s[index]=='0' and len(s[index:i+1])>1:\n",
    "                        continue\n",
    "                    path.append(s[index:i+1])\n",
    "                    backTrace(i+1)\n",
    "                    path.pop()\n",
    "        backTrace(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        segCount = 4\n",
    "        segments = [0] * segCount\n",
    "        ans = []\n",
    "        def dfs(segID,segStart):\n",
    "            if segID == segCount:\n",
    "                if segStart == len(s):\n",
    "                    tmp = '.'.join(str(seg) for seg in segments)\n",
    "                    ans.append(tmp)\n",
    "                return\n",
    "            \n",
    "            if segStart == len(s):\n",
    "                return\n",
    "            \n",
    "            if s[segStart] == '0':\n",
    "                segments[segID] = 0\n",
    "                dfs(segID+1,segStart+1)\n",
    "\n",
    "            add = 0\n",
    "            for segEnd in range(segStart,len(s)):\n",
    "                # add = add *10 + ord(s[segEnd]) - ord('0')\n",
    "                add = add*10 + int(s[segEnd])\n",
    "                if 0 < add <= 255:\n",
    "                    segments[segID] = add\n",
    "                    dfs(segID+1,segEnd+1)\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        SEG_COUNT = 4\n",
    "        ans = list()\n",
    "        segments = [0] * SEG_COUNT\n",
    "        \n",
    "        def dfs(segId: int, segStart: int):\n",
    "            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案\n",
    "            if segId == SEG_COUNT:\n",
    "                if segStart == len(s):\n",
    "                    ipAddr = \".\".join(str(seg) for seg in segments)\n",
    "                    ans.append(ipAddr)\n",
    "                return\n",
    "            \n",
    "            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯\n",
    "            if segStart == len(s):\n",
    "                return\n",
    "\n",
    "            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0\n",
    "            if s[segStart] == \"0\":\n",
    "                segments[segId] = 0\n",
    "                dfs(segId + 1, segStart + 1)\n",
    "                return\n",
    "            \n",
    "            # 一般情况，枚举每一种可能性并递归\n",
    "            addr = 0\n",
    "            for segEnd in range(segStart, len(s)):\n",
    "                addr = addr * 10 + (ord(s[segEnd]) - ord(\"0\"))\n",
    "                if 0 < addr <= 0xFF:\n",
    "                    segments[segId] = addr\n",
    "                    dfs(segId + 1, segEnd + 1)\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        self.res = []\n",
    "        if len(s)>12 or len(s)<4:return []\n",
    "        def check(s):\n",
    "            if len(s)<=0 or len(s)>3:return False\n",
    "            if s[0]=='0' and len(s)>1:return False\n",
    "            if eval(s)<0 or eval(s)>255:return False\n",
    "            return True\n",
    "        @lru_cache\n",
    "        def dfs(loc):\n",
    "            if loc[0]!=-1 and loc[1]!=-1 and loc[2]!=-1:\n",
    "                if check(s[loc[-1]+1:]):\n",
    "                    self.res.append(s[:loc[0]+1]+'.'+s[loc[0]+1:loc[1]+1]+'.'+s[loc[1]+1:loc[2]+1]+'.'+s[loc[2]+1:])\n",
    "                return \n",
    "            if loc[0]==-1:\n",
    "                for i in range(len(s)):\n",
    "                    if check(s[:i+1]):dfs((i,-1,-1))\n",
    "            elif loc[1]==-1:\n",
    "                for i in range(loc[0]+1,len(s)):\n",
    "                    if check(s[loc[0]+1:i+1]):dfs((loc[0],i,-1))\n",
    "            else:\n",
    "                for i in range(loc[1]+1,len(s)):\n",
    "                    if check(s[loc[1]+1:i+1]):dfs((loc[0],loc[1],i))\n",
    "        dfs((-1,-1,-1))\n",
    "        return self.res   \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        SEG_COUNT = 4\n",
    "        ans = list()\n",
    "        segments = [0] * SEG_COUNT\n",
    "        \n",
    "        def dfs(segId: int, segStart: int):\n",
    "            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案\n",
    "            if segId == SEG_COUNT:\n",
    "                if segStart == len(s):\n",
    "                    ipAddr = \".\".join(str(seg) for seg in segments)\n",
    "                    ans.append(ipAddr)\n",
    "                return\n",
    "            \n",
    "            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯\n",
    "            if segStart == len(s):\n",
    "                return\n",
    "\n",
    "            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0\n",
    "            if s[segStart] == \"0\":\n",
    "                segments[segId] = 0\n",
    "                dfs(segId + 1, segStart + 1)\n",
    "            \n",
    "            # 一般情况，枚举每一种可能性并递归\n",
    "            addr = 0\n",
    "            for segEnd in range(segStart, len(s)):\n",
    "                addr = addr * 10 + (ord(s[segEnd]) - ord(\"0\"))\n",
    "                if 0 < addr <= 0xFF:\n",
    "                    segments[segId] = addr\n",
    "                    dfs(segId + 1, segEnd + 1)\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        \n",
    "        def is_valid(s:str)->bool:\n",
    "            n = len(s)\n",
    "            if n >3:\n",
    "                return False\n",
    "            res  = 0\n",
    "            for  i  in range(len(s)):\n",
    "                res = res*10 +int(s[i])\n",
    "            if  res >255:\n",
    "                return False\n",
    "            if n >=2:\n",
    "                return s[0] !='0'\n",
    "            return True \n",
    "        res = []\n",
    "        def trackback(index:int,path:List[str],num:int):\n",
    "            if  index ==len(s) and  num==4:\n",
    "                iaddr = '.'.join(path.copy())\n",
    "                res.append(iaddr)\n",
    "                return  \n",
    "            if  num>4:\n",
    "                return \n",
    "            for  i in range(index,len(s)):\n",
    "                if is_valid(s[index:i+1]):\n",
    "                    path.append(s[index:i+1])\n",
    "                    trackback(i+1,path,num+1)\n",
    "                    path.pop()\n",
    "        trackback(0,[],0)\n",
    "        return res \n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        if n > 12:return []\n",
    "        def dfs(index,stack,num):\n",
    "            if index == n and len(stack) == 4:\n",
    "                new = '.'.join([str(a) for a in stack])\n",
    "                if len(new) == n+3:\n",
    "                    ans.append(new)\n",
    "                return\n",
    "            res = 0\n",
    "            for i in range(index,n):\n",
    "                res = res*10+int(s[i])\n",
    "                if res > 255:\n",
    "                    continue\n",
    "                #elif stack and num == 0:\n",
    "                #    break\n",
    "                stack.append(res)\n",
    "                dfs(i+1,stack,res)\n",
    "                stack.pop()\n",
    "        ans = []\n",
    "        dfs(0,[],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        SEG_COUNT = 4\n",
    "        ans = list()\n",
    "        segments = [0] * SEG_COUNT\n",
    "        \n",
    "        def dfs(segId: int, segStart: int):\n",
    "            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案\n",
    "            if segId == SEG_COUNT:\n",
    "                if segStart == len(s):\n",
    "                    ipAddr = \".\".join(str(seg) for seg in segments)\n",
    "                    ans.append(ipAddr)\n",
    "                return\n",
    "            \n",
    "            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯\n",
    "            if segStart == len(s):\n",
    "                return\n",
    "\n",
    "            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0\n",
    "            if s[segStart] == \"0\":\n",
    "                segments[segId] = 0\n",
    "                dfs(segId + 1, segStart + 1)\n",
    "            \n",
    "            # 一般情况，枚举每一种可能性并递归\n",
    "            addr = 0\n",
    "            for segEnd in range(segStart, len(s)):\n",
    "                addr = addr * 10 + (ord(s[segEnd]) - ord(\"0\"))\n",
    "                if 0 < addr <= 0xFF:\n",
    "                    segments[segId] = addr\n",
    "                    dfs(segId + 1, segEnd + 1)\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        i = 1\n",
    "        while i<4 and i<n-2:\n",
    "            j = i+1\n",
    "            while j<i+4 and j<n-1:\n",
    "                k = j+1\n",
    "                while k<j+4 and k<n:\n",
    "                    if n-k>3:\n",
    "                        k+=1\n",
    "                        continue\n",
    "                    a = s[0:i]\n",
    "                    b = s[i:j]\n",
    "                    c = s[j:k]\n",
    "                    d = s[k:]\n",
    "                    if int(a)>255 or int(b)>255 or int(c)>255 or int(d)>255:\n",
    "                        k+=1\n",
    "                        continue\n",
    "                    if (len(a)!=1 and a[0]=='0') or (len(b)!=1 and b[0]=='0') or(len(c)!=1 and c[0]=='0') or (len(d)!=1 and d[0]=='0'): \n",
    "                        k+=1\n",
    "                        continue\n",
    "                    temp = a+'.'+b+'.'+c+'.'+d\n",
    "                    res.append(temp)\n",
    "                    k+=1\n",
    "                j+=1\n",
    "            i+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        n = len(s)\n",
    "\n",
    "        def is_valid(segment):\n",
    "            if len(segment) > 1 and segment[0] == '0':\n",
    "                return False \n",
    "            if 0 <= int(segment) <= 255:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        def back_track(start, path):\n",
    "            print(start)\n",
    "            if len(path) == 4 and start >= n:\n",
    "                result.append(\".\".join(path))\n",
    "                return\n",
    "            elif len(path) == 4:\n",
    "                return\n",
    "            \n",
    "            for end in range(start + 1, min(start + 4, n + 1)):\n",
    "                segment = s[start:end]\n",
    "                if is_valid(segment):\n",
    "                    path.append(segment)\n",
    "                    back_track(end, path)\n",
    "                    path.pop()\n",
    "        \n",
    "        back_track(0, [])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def backtrack(start=0, parts=[]):\n",
    "            # Base case: if we have 4 parts and have used all characters in the string\n",
    "            if len(parts) == 4 and start == len(s):\n",
    "                result.append(\".\".join(parts))\n",
    "                return\n",
    "            \n",
    "            # If we already have 4 parts but still have characters left in the string, stop\n",
    "            if len(parts) == 4:\n",
    "                return\n",
    "            \n",
    "            for end in range(start + 1, len(s) + 1):\n",
    "                # Extract the current part from the string and validate it\n",
    "                part = s[start:end]\n",
    "                \n",
    "                if len(part) > 1 and part[0] == '0':  # Eliminate parts with leading zeros\n",
    "                    return\n",
    "                \n",
    "                if 0 <= int(part) <= 255:  # Check if it's a valid segment\n",
    "                    backtrack(end, parts + [part])\n",
    "                else:  # No need to check further as it will only create invalid segments\n",
    "                    break\n",
    "        \n",
    "        result = []\n",
    "        backtrack()\n",
    "        return result\n",
    "\n",
    "# Test the function\n",
    "sol = Solution()\n",
    "print(sol.restoreIpAddresses(\"25525511135\"))\n",
    "print(sol.restoreIpAddresses(\"0000\"))\n",
    "print(sol.restoreIpAddresses(\"010010\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if True:\n",
    "            if len(s) > 12:\n",
    "                return []\n",
    "            path,res = [],[]\n",
    "            def backTrace(index):\n",
    "                if index > len(s):\n",
    "                    return\n",
    "                if index == len(s) and len(path) == 4:\n",
    "                    res.append('.'.join(path))\n",
    "                    return\n",
    "                for i in range(index,len(s)):\n",
    "                    if 0 <= int(s[index:i+1]) <= 255:\n",
    "                        # 处理前导0情形\n",
    "                        if s[index] == '0' and len(s[index:i+1]) > 1:\n",
    "                            continue\n",
    "                        path.append(s[index:i+1])\n",
    "                        backTrace(i+1)\n",
    "                        path.pop()\n",
    "            backTrace(0)\n",
    "            return res\n",
    "\n",
    "        elif False:\n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if \"\".join(paths) == s and len(paths) == 4:\n",
    "                    results.append(\".\".join(paths))\n",
    "                    return\n",
    "                if len(paths)>4:\n",
    "                    return\n",
    "                for i in range(index, len(s)):\n",
    "                    subpath = s[index:i+1]\n",
    "                    if int(subpath)<0 or int(subpath)>255:\n",
    "                        continue\n",
    "                    if len(subpath) >=2 and subpath.startswith(\"0\"):\n",
    "                        continue\n",
    "                    dfs(paths + [s[index:i+1]], i+1)\n",
    "            dfs([], 0)\n",
    "            return results\n",
    "\n",
    "        else:\n",
    "            results = []\n",
    "\n",
    "            def dfs(paths, index):\n",
    "                if \"\".join(paths) == s and len(paths) == 4:\n",
    "                    results.append(paths)\n",
    "                    return\n",
    "                if len(paths) >4:\n",
    "                    return\n",
    "\n",
    "                for i in range(index,len(s)):\n",
    "                    t = s[index:i+1]\n",
    "                    if not (int(t) >=0 and int(t) <=255):\n",
    "                        continue \n",
    "                    if len(t)>=2 and t.startswith(\"0\"):\n",
    "                        continue\n",
    "                    dfs(paths +[s[index:i+1]], i+1)\n",
    "            dfs([], 0)\n",
    "            print(results)\n",
    "            results = [\".\".join(i) for i in results]\n",
    "            return results"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
